package com.sise.Linked;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 *      23. 合并K个升序链表
 *
 *      给你一个链表数组，每个链表都已经按升序排列。
 *      请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 *      输入：lists = [[1,4,5],[1,3,4],[2,6]]
 *      输出：[1,1,2,3,4,4,5,6]
 *
 *      [
 *        1->4->5,
 *        1->3->4,
 *        2->6
 *      ]
 *      将它们合并到一个有序链表中得到。
 *      1->1->2->3->4->4->5->6
 *
 *  题解 1：
 *      用最小堆优先队列，把链表的头结点都放进去，然后出队当前优先队列中最小的，挂上链表，
 *      然后让出队的那个节点的下一个入队，再出队当前优先队列中最小的，直到优先队列为空。
 *
 *      这里利用的是优先级队列的比较，帮助我们进行排序。每次只需要在队列中放入 lists.length 长度的数值，在取出来的时候，判断下一位是否还要值，
 *      若存在数值，那么就将其放入到优先级队列中，进行再一次的排序。
 *
 *  题解 2：
 *      从链表中间进行切割，知道剩下一或二条链表，然后对链表进行两两合并
 */
public class _23_mergeKLists {

    /**
     * 题解 1：利用优先队列进行存储并取出
     */
    public ListNode mergeKLists(ListNode[] lists) {

        if (lists == null || lists.length == 0) return null;

        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {          // 创建优先级队列，最小堆
            @Override
            public int compare(ListNode o1, ListNode o2) {
                if (o1.val < o2.val) return -1;
                else if (o1.val == o2.val) return 0;
                else return 1;
            }
        });

        ListNode dummy = new ListNode(0);                   // 创建哑结点
        ListNode p = dummy;

        for (ListNode node : lists) {                           // 将链表头结点添加到优先级队列中，这里只是头结点，如何保证全部节点
            if (node != null) queue.add(node);
        }

        while (!queue.isEmpty()) {
            p.next = queue.poll();                              // 取出链表的头结点(或此时队列中的最小值)，赋值给 p.next
            p = p.next;                                         // 将 p 往后移动一步
            if (p.next != null) queue.add(p.next);              // 由于此时头结点已经出队列了，故此我们判断其下一个节点是否存在，若存在则入队 queue.add()
        }
        return dummy.next;
    }

    /**
     * 题解 2：利用链表双双合并
     */
    public ListNode mergeKLists_2(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);               // 归并
    }

    private ListNode merge(ListNode[] lists, int left, int right) {      // 使用递归，这里主要是为了将链表等分切割。返回的结果经过 mergeTwoList() 处理，已经是排序完的链表了
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;                             // 从中间节点不断的分割，直到剩下 一或两个 链表头节点 list1 和 list2，此时将它们进合并
        ListNode list1 = merge(lists, left, mid);
        ListNode list2 = merge(lists, mid + 1, right);
        return mergeTwoList(list1, list2);                               // 传入两条链表的头结点，对其进行合并
    }

    /**
     *      递归三部曲：
     *      1、终止条件：当有一条链表的数值为空
     *      2、找返回值：返回排序完的链表
     *      3、本次递归：找出哪条链表的数值更小，将 min.next => 排序完的链表（与 offer25 不同，这里由于没有创建新节点，故此会破坏原有链表的结构）
     */
    private ListNode mergeTwoList(ListNode list1, ListNode list2) {      // 双链表的合并，
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val < list2.val) {                                     // 双链表进行比较，找出较小值，将 min.val 指向递归后的链表（排在最前面的也是最小值）。返回已经排好序的链表
            list1.next = mergeTwoList(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoList(list1, list2.next);
            return list2;
        }
    }
}